//nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 
//
// 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。 
//
// 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 
//nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 
//
// 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
//输出：[-1,3,-1]
//解释：nums1 中每个值的下一个更大元素如下所述：
//- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
//- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
//- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 
//
// 示例 2： 
//
// 
//输入：nums1 = [2,4], nums2 = [1,2,3,4].
//输出：[3,-1]
//解释：nums1 中每个值的下一个更大元素如下所述：
//- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
//- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums1.length <= nums2.length <= 1000 
// 0 <= nums1[i], nums2[i] <= 10⁴ 
// nums1和nums2中所有整数 互不相同 
// nums1 中的所有整数同样出现在 nums2 中 
// 
//
// 
//
// 进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？ 
// Related Topics 栈 数组 哈希表 单调栈 👍 715 👎 0

package leetcode.editor.cn;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

class NextGreaterElementI {
    public static void main(String[] args) {
        Solution solution = new NextGreaterElementI().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 时间复杂度O(n * n * n)
         *
         * @param nums1
         * @param nums2
         * @return
         */
//        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//            int[] res = new int[nums1.length];  // 结果集
//            // 初始化，没有最大值就返回1
//            for (int i = 0; i < res.length; i++) {
//                res[i] = -1;
//            }
//            HashMap<Integer, Integer> map = new HashMap<>();    // 表示这个元素key的右边第一个比它大的值是map.get(key)
//            Stack<Integer> stack = new Stack<>();
//            stack.push(0);
//
//            // 由于nums1时nums2的子集，所以每日温度相差不大，使用单调栈即可解决
//            for (int i = 1; i < nums2.length; i++) {
//                while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
//                    map.put(nums2[stack.peek()], nums2[i]);
//                    stack.pop();
//                }
//                stack.push(i);
//            }
//
//            // map中搜索是否由nums1的值
//            for (int i = 0; i < nums1.length; i++) {
//                if (map.containsKey(nums1[i])) {
//                    res[i] = map.get(nums1[i]);
//                }
//            }
//
//            return res;
//        }

        /**
         * 时间复杂度O(n * n)，使用map来记录nums1
         *
         * @param nums1
         * @param nums2
         * @return
         */
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] res = new int[nums1.length];  // 结果集
            Arrays.fill(res, -1);   // 全部赋值为-1
            HashMap<Integer, Integer> map = new HashMap<>();    // 用来记录nums1出现的元素和数组下标
            for (int i = 0; i < nums1.length; i++) {
                map.put(nums1[i], i);
            }

            Stack<Integer> stack = new Stack<>();
            stack.push(0);

            for (int i = 1; i < nums2.length; i++) {
                while (!stack.isEmpty() && nums2[stack.peek()] < nums2[i]) {
                    if (map.containsKey(nums2[stack.peek()])) { // nums1中存在再加入结果集
                        res[map.get(nums2[stack.peek()])] = nums2[i];
                    }
                    stack.pop();
                }
                stack.push(i);
            }

            return res;
        }

        /*public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] greater = nextGreaterElement(nums2);
            // 转化为映射
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums2.length; i++) {
                map.put(nums2[i], greater[i]);
            }

            int[] res = new int[nums1.length];
            for (int i = 0; i < nums1.length; i++) {
                res[i] = map.get(nums1[i]);
            }

            return res;
        }

        // 参照labuladong的模板：https://labuladong.gitee.io/algo/2/22/62/
        int[] nextGreaterElement(int[] nums) {
            int n = nums.length;
            int[] res = new int[n];
            Stack<Integer> stack = new Stack<>();
            for (int i = n - 1; i >= 0; i--) {
                while (!stack.isEmpty() && stack.peek() <= nums[i]) {
                    stack.pop();
                }

                res[i] = stack.isEmpty() ? -1 : stack.peek();
                stack.push(nums[i]);
            }

            return res;
        }*/
    }
//leetcode submit region end(Prohibit modification and deletion)

}
